package br.ufrn.ciencomp.grafos;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;

import br.ufrn.ciencomp.grafos.Grafo.Tipo;

public class Floyd {
	private static int[][] dist;
	private static int[][] pre;
	private static boolean floyd = false;
	
	public static void floydWarshall(Grafo g) {
		dist = new int[g.getN()][g.getN()];
		pre = new int[g.getN()][g.getN()];
		
		for(int i = 0; i < g.getN(); i++) {
			for(int j = 0; j < g.getN(); j++) {
				pre[i][j] = -1;
				if(i != j) {
					if(g.getMatrizAdj()[i][j] != 0) {
						dist[i][j] = g.getMatrizAdj()[i][j];
						pre[i][j] = i;
					} else {
						dist[i][j] = 9999;
					}
				} else {
					dist[i][j] = 0;
				}
			}
		}
		
		for(int k = 0; k < g.getN(); k++) {
			for(int i = 0; i < g.getN(); i++) {
				for(int j = 0; j < g.getN(); j++) {
					if(dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						pre[i][j] = pre[k][j];
					}
				}
			}
		}
		
		floyd = true;
		
	}
	
	public static void caminho(int i, int j) {
		if(i == j)
			System.out.print(i + " ");
		else if(pre[i][j] == -1) {
			System.out.println("No path");
		} else {
			caminho(i, pre[i][j]);
			System.out.print(j + " ");
		}
	}
		
	public static void main(String args[]) {
		try {
			Scanner scanner = new Scanner(new File("streams/floyd2.in"));
			
			Grafo g = new Grafo(scanner.nextInt(), Tipo.MATRIZ);
			System.out.println("-");
			int inicio, fim;
			
			while(scanner.hasNext()) {
				String instrucao = scanner.next();
				if(instrucao.startsWith("edge")) {
					g.addAresta(
							scanner.nextInt(), 
							scanner.nextInt(), 
							scanner.nextInt());
					System.out.println("-");
				} else if(instrucao.equals("shortest")) {
					if(!floyd) {
						floydWarshall(g);
					}
					
					inicio = scanner.nextInt();
					fim = scanner.nextInt();
					caminho(inicio, fim);
					System.out.println(dist[inicio][fim]);
				}
			}
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
}
